package main

import "fmt"

/**
 * @param s: a string
 * @param k: an integer
 * @return: return an integer
 */
func LongestSubstring(s string, k int) int {
	/*
	   思路
	   一、分治法
	   对于该问题，通过观察不难发现字符串中出现频次少于所要求频次k的字符，一定不会出现在所求的最长子串当中，
	   则利用这一性质可以对整个字符串进行分割，
	   分割为左右两个子串，再分别求解左右子串的最长子串，
	   在所有符合题设的最长子串当中找出长度最长的子串并返回其长度即可完成题目要求。由此可以确立能够使用分治方法进行解题。

	   具体思路为：
	   先将整个字符串遍历一编，统计每个字符出现的频次从头开始遍历字符串，
	   若是发现当前字符所出现频次小于要求的频次，
	   则说明再所求的最长子串当中不会包含这个字符，
	   则可将整个字符串分解为求解当前所遍历的字符为分割点的左子串和右子串的最长子串中的最大值。举例：

	   对于一个字符串来说，如果要求子串最少出现k次，那么如果某些字母出现的次数小于k,
	   这些字母一定不会出现在最长的子串中，并且这些字母将整个字符子串分割成小段，这些小段有可能是最长的
	   但是由于被分割了，还是要检查这一小段，如果某些字母出现的次数小于k,会将小段继续分割下去,
	   比如字符串"aacbbbdc"，要求最少出现2次,我们记录左右闭区间，，
	   第一轮[0,7]，处理"aacbbbdc"，d只出现了一次不满足，于是递归解决区间[0,5]、[7,7]
	   第二轮[0,5]，处理"aacbbb"，  c只出现了一次不满足，于是递归解决区间[0,1]、[3,4]
	   第二轮[7,7]，处理"c"，       c只出现了一次不满足，不继续递归
	   第三轮[0,1]，处理"aa"，      满足出现次数>=2,ret=2
	   第三轮[3,4]，处理"bbb"，     满足出现次数>=2 ret=3;


	     注意代码实现中，通常分治和递归是伴生的，因为将大问题拆分为同等子问题，
	   得到子问题的答案并更新大问题答案就意味着递归调用的产生。
	   牵扯到递归，有三大要素，分别是返回条件、本层递归中的行为和返回值。
	   对于返回条件和返回值：①如果k不大于2，则可直接返回s的长度；②若是s为空，或s长度小于k直接返回0；
	   ③若是整个字符串中的字符出现频次都大于等于k，则直接返回字符串的长度；
	   ④否则返回分割后的左右子串的最长子串长度中较大值；
	   对于本层中的递归动作，就是找出分割点/区间，进行递归调用。
	*/
	if k <= 1 {
		return len(s)
	}

	if len(s) == 0 || len(s) < k {
		return 0
	}

	hash := make([]int, 26)
	for i := 0; i < len(s); i++ {
		hash[s[i]-'a']++
	}

	i := 0
	for i < len(s) && hash[s[i]-'a'] >= k {
		i++
	}

	if i == len(s) {
		return len(s)
	}

	l := LongestSubstring(s[0:i], k)
	//优化操作，将分割点进行拓展，找到分割子串，一直将i遍历至出现频次>=k的字符位置
	for i < len(s) && hash[s[i]-'a'] < k {
		i++
	}
	r := LongestSubstring(s[i:], k)

	ans := l
	if ans < r {
		ans = r
	}
	return ans
}

func main() {
	fmt.Println(LongestSubstring("aaabb", 3))
	fmt.Println(LongestSubstring("ababbc", 2))

}

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有207条未读消息，请及时查看
1261 · 字符至少出现K次的最长子串
算法
中等
通过率
45%

题目
题解12
笔记
讨论37
排名
记录
描述
找出给定字符串的最长子串，使得该子串中的每一个字符都出现了至少k次，返回这个子串的长度。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1：

输入：
s = "aaabb", k = 3
输出：
3
解释：
最长子串为"aaa"，因为'a'重复了3次。
样例2：

输入：
s = "ababbc", k = 2
输出：
5
解释：
最长子串为"ababb"，因为'a'重复了2次，同时'b'重复了3次。
标签
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
12345678
/**
 * @param s: a string
 * @param k: an integer
 * @return: return an integer
func LongestSubstring(s string, k int) int {
	// write your code here
}
控制台
历史提交

*/
